package com.mid;
/**
 * Created by Lxk on 2019/3/17.
 */
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}
public class Solution86 {
    public ListNode partition(ListNode head, int x) {
        if(head == null){
            return null;
        }
        ListNode bigHead = null;
        ListNode bigEnd = null;
        ListNode lessHead = null;
        ListNode lessEnd = null;
        while(head != null){
            if(head.val>x){
                if(bigHead == null){
                    bigHead = head;
                    bigEnd = bigHead;
                    head = head.next;
                    bigHead.next = null;
                }else{
                    bigEnd.next = head;
                    bigEnd = bigEnd.next;
                    head = head.next;
                    bigEnd.next = null;
                }
            }else{
                if(lessHead == null){
                    lessHead = head;
                    lessEnd = lessHead;
                    head = head.next;
                    lessHead.next = null;
                }else{
                    lessEnd.next = head;
                    lessEnd = lessEnd.next;
                    head = head.next;
                    lessEnd.next = null;
                }
            }
        }
        if(lessEnd != null){
            lessEnd.next = bigHead;
            return lessHead;
        }else{
            return bigHead;
        }
    }
}
